翻訳と辞書 Words near each other ・ Cyclic number (group theory) ・ Cyclic olefin copolymer ・ Cyclic order ・ Cyclic ozone ・ Cyclic peptide ・ Cyclic permutation ・ Cyclic Poets ・ Cyclic polytope ・ Cyclic prefix ・ Cyclic pump ・ Cyclic pyranopterin monophosphate ・ Cyclic pyranopterin monophosphate synthase ・ Cyclic quadrilateral ・ Cyclic reduction ・ Cyclic redundancy check ・ Cycle basis ・ Cycle button ・ Cycle chic ・ Cycle Collstrop ・ Cycle Computing ・ Cycle count ・ Cycle cover ・ Cycle decomposition ・ Cycle decomposition (graph theory) ・ Cycle detection ・ Cycle double cover ・ Cycle for Declamation ・ Cycle for Survival ・ Cycle Force Group ・ Cycle Friendly Awards Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Cycle basis ： ウィキペディア英語版 Cycle basis In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every Eulerian subgraph to be expressed as a symmetric difference of basis cycles. A fundamental cycle basis may be formed from any spanning tree or spanning forest of the given graph, by selecting the cycles formed by the combination of a path in the tree and a single edge outside the tree. Alternatively, if the edges of the graph have positive weights, the minimum weight cycle basis may be constructed in polynomial time. In planar graphs, the set of bounded cycles of an embedding of the graph forms a cycle basis. The minimum weight cycle basis of a planar graph corresponds to the Gomory–Hu tree of the dual graph. ==Definitions== A spanning subgraph of a given graph ''G'' has the same set of vertices as ''G'' itself but, possibly, fewer edges. A graph ''G'', or one of its subgraphs, is said to be Eulerian if each of its vertices has even degree (its number of incident edges). Every simple cycle in a graph is an Eulerian subgraph, but there may be others. The cycle space of a graph is the collection of its Eulerian subgraphs. It forms a vector space over the two-element finite field. The vector addition operation is the symmetric difference of two or more subgraphs, which forms another subgraph consisting of the edges that appear an odd number of times in the arguments to the symmetric difference operation.〔.〕 A cycle basis is a basis of this vector space in which each basis vector represents a simple cycle. It consists of a set of cycles that can be combined, using symmetric differences, to form every Eulerian subgraph, and that is minimal with this property. Every cycle basis of a given graph has the same number of cycles, which equals the dimension of its cycle space. This number is called the circuit rank of the graph, and it equals $m-n+c$ where $m$ is the number of edges in the graph, $n$ is the number of vertices, and $c$ is the number of connected components.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Cycle basis」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.